為什麼選此主題？

一直以來，Leetcode 都被認為是最受軟體工程師歡迎的程式語言撰寫練習平台之一，其中，有幾個讓該平台廣受喜愛的原因：海量考古題、支援多種程式語言、直覺介面、解題社群與企業題庫服務。因此在這鐵人賽中，我有了想嘗試 LeetCode 考題的想法，我將利用 30 天的自主學習時間，從 FB 工程師挑選的經典題目中進行練習與理解。我也會將自學過程分享給大家，希望也能對各位有所幫助。

DAY 1 試題

問題描述

給定一個未排序的整數數組，返回最長的連續元素序列的長度。我們必須設計一個時間複雜度為 O(n) 的算法來解決這個問題。
如題目: [100,4,200,1,3,2] 。找到最長的連續序列為 [1,2,3,4] ，因此正確輸出為 4 。

解題思路

為了在 O(n) 時間複雜度內解決這個問題，我們可以使用哈希集合（unordered_set）來高效地檢查數字的存在性。具體的解題步驟如下：

1. 使用哈希集合：我們首先將所有數字存儲到一個哈希集合中，這樣可以實現 O(1) 時間複雜度的查找操作。
2. 遍歷集合中的每個數字：對於每個數字，我們檢查它是否為某個連續序列的起點。如果 num - 1 不在集合中，那麼 num 是一個潛在的序列起點。
3. 擴展序列：從這個序列的起點開始，檢查 num + 1, num + 2, num + 3 等數字是否存在於集合中，並計算序列的長度。
4. 更新最長序列長度：在遍歷所有數字後，記錄下最長的連續序列長度。

何謂哈希集合及為什需使用

哈希集合（Hash Set）是一種基於哈希表的數據結構，用於高效地存儲和查找唯一元素。它的主要特點包括：
1. 快速查找：平均查找、插入和刪除操作的時間複雜度為 O(1)。
2. 無序性：集合中的元素無特定順序。
3. 唯一性：不允許重複元素。

解題過程如下圖:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : numSet) {
            // 如果 num - 1 不在 set 中，說明這是序列的起點
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;

                // 找到 num+1, num+2, num+3... 連續的數字
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }

                // 更新最長的連續序列長度
                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

最後加入主要最後加入程式的進入點來實現整體操作:

int Main() {
    string input;
    getline(cin, input);  // 讀取整行輸入
    
    // 移除方括號
    input = input.substr(1, input.size() - 2);
    
    vector<int> nums;
    stringstream ss(input);
    string temp;
    
    // 使用逗號分隔數字並存入 vector
    while (getline(ss, temp, ',')) {
        nums.push_back(stoi(temp));  // 將字串轉換為整數並存入 nums
    }

    // 創建 Solution 類別的實例並調用 longestConsecutive 函數
    Solution sol;
    int result = sol.longestConsecutive(nums);
    cout << result << endl;

    return 0;
}

完整程式碼:

#include <iostream>
#include <sstream>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : numSet) {
            // 如果 num - 1 不在 set 中，說明這是序列的起點
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;

                // 找到 num+1, num+2, num+3... 連續的數字
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }

                // 更新最長的連續序列長度
                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

int Main() {
    string input;
    getline(cin, input);  // 讀取整行輸入
    
    // 移除方括號
    input = input.substr(1, input.size() - 2);
    
    vector<int> nums;
    stringstream ss(input);
    string temp;
    
    // 使用逗號分隔數字並存入 vector
    while (getline(ss, temp, ',')) {
        nums.push_back(stoi(temp));  // 將字串轉換為整數並存入 nums
    }

    // 創建 Solution 類別的實例並調用 longestConsecutive 函數
    Solution sol;
    int result = sol.longestConsecutive(nums);
    cout << result << endl;

    return 0;
}

以上是第一天的自學內容分享，謝謝大家。